607A - Chain Reaction - CodeForces Solution

#include <bits/stdc++.h>
using namespace std;

int pos[100010], power[1000010];
int aux[100010];
int d[100010];

int main(){
    int n; scanf("%d", &n);
    for(int i = 0;i < n;i++){
        int a,b; scanf("%d %d", &a, &b);
        pos[i] = a;
        //power[pos[i]] = b;
        power[a] = b;
    }
    sort(pos, pos + n);
    aux[0] = 0;
    for(int i = 1;i < n;i++){
        int id = lower_bound(pos,pos + n, pos[i] - power[pos[i]]) - pos;
        aux[i] = i - id;
    }
    
    for(int i = 1;i < n;i++){
        int id = lower_bound(pos, pos + n, pos[i] - power[pos[i]]) - pos;
        d[i] = d[id - 1] + aux[i];
    }
    int resp = 100010;
    for(int i = 0;i < n;i++){
        resp = min(resp, (d[i] + n - i - 1) );
    }
    printf("%d", resp);
}